/* Grupo 8:
Caio Augusto da Silva Gomes - 7239072
Francisco Angelo Cabelo - 7277652
Gabriela Ruch Salmeron - 7239350
*/

#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>

#include <omp.h>
#define NTHREADS 4 //Numero de threads a ser usado

#define MAXJUNCOES 1010
#define INTMAX 2147483646

//Cria a matriz de custos
int custos[MAXJUNCOES*MAXJUNCOES];

//Funcao que calcula o caminho com o menor custo de um ponto ao outro
int Dijkstra(int origem, int destino, int vertices, int * vres){
    int menor, i, j;
    float vdijs[2][MAXJUNCOES];
    int visitado[MAXJUNCOES];

    //Linha de comando que paraleliza o loop com o numero de threads especificado
    #pragma omp parallel for num_threads(NTHREADS)
    for (i=0; i < vertices; i++) {
        visitado[i] = 0;
        vdijs[0][i] = INTMAX; /* guarda o custo */
        vdijs[1][i] = -1; /* vetor de antecedencia */
    }

    vdijs[0][origem] = 0;
    vdijs[1][origem] = origem;

    for (i=0; i < vertices; i++) {
        #pragma omp parallel for num_threads(NTHREADS)
        for (j=0; j< vertices; j++) {
            if (custos[origem*vertices + j])
                if (vdijs[0][j] > vdijs[0][origem] + custos[origem*vertices + j]) {
                    vdijs[0][j] = vdijs[0][origem] + custos[origem*vertices + j];
                    vdijs[1][j] = origem;
                }
            }

        visitado[origem] = 1;
        menor = origem;

        #pragma omp parallel for num_threads(NTHREADS)
        for (j=0; j < vertices; j++) {
            if (!visitado[j] && vdijs[0][j] != INTMAX) {
                if (menor == origem) {
                menor = j;
                } else if (vdijs[0][j] < vdijs[0][menor]) {
                menor = j;
                }
            }
        }

    origem = menor;
    }

    #pragma omp parallel for num_threads(NTHREADS)
    for (i=0; i < vertices; i++) {
       vres[i] = vdijs[0][i];
    }
    return 0;
}


int main(int argc, char **argv)
{
     int div, n,m,i,j, juncao, vert, total;
    int maior = 2147483646;
      int noProcesses,
      processId = 0,
      source,
      destino;

      MPI_Status status;
      MPI_Init(&argc,&argv);
      MPI_Comm_rank(MPI_COMM_WORLD,&processId);
      MPI_Comm_size(MPI_COMM_WORLD,&noProcesses);
       // Entrando no processo Mestre!
      if (processId == 0)
      {
    // Recebe o numero de juncoes n e o numero de ruas m
        scanf("%d %d ", &n, &m );

    //Verifica se n esta entre 2 e MAXJUNCOES
    if ( n < 2 || n > MAXJUNCOES){
        printf("O valor de n deve estar entre 2 < n < MAXJUNCOES\n");
        return 1;
    }

    //Verifica se m entre (n-1) < m < ((n(n-1))/2)
    if ( m < (n-1) || m > ((n*(n-1))/2) ) {
        printf("O valor de m deve estar entre (n-1) < m < ((n(n-1))/2)) \n");
        return 1;
    }

    //Matriz que recebe as linhas das ruas
    int ruas[3][m];

    //Recebe Ai e Bi (juncao) e o custo Wi
    for (i=0; i<m; i++){
    scanf("%d %d %d ", &ruas[0][i], &ruas[1][i], &ruas[2][i] );
    }

    //Inicializa a matriz de custos com zero: zero signinifica que nao ha juncao entre as ruas na implementacao deste algoritmo de Dijkstra.
        for(j=0; j<n*n; j++)
            custos[j]=0;

    //Monta o vetor de custos a partir da matriz das ruas
    for (i=0; i<m; i++){
        int a = ruas[0][i];
        int b = ruas[1][i];
        int custo = ruas[2][i];
        // Dica: linha*ncoluna + coluna;
        custos[(a-1)*n + b-1] = custo;
        custos[(b-1)*n + a-1] = custo;
    }

      // verifica quantas vezes ira fazer a interacao.
       int divisao = n/(noProcesses-1);
        // Se tem resto, faz a interacao mais uma vez.
       if (n%(noProcesses -1) > 0)
          divisao++;
      // Se tem mais processos que vertices, rodará para todos os processos apenas 1 vez.
       if (noProcesses > n+1)
          divisao =  1;

        // numero do vertice a ser enviado.
       vert = 0;

       // printf("<%d %d> ", divisao, vert);

        // Precisa de n+1 processos (n filhos) para n vertices, para melhor eficiencia.
         for(destino=1; destino<noProcesses; destino++){
         // Envio das variaveis para os outros processos
           MPI_Send(&n, 1, MPI_INT, destino, 1, MPI_COMM_WORLD);
         // Envio de uma variavel com a quantidade de vertices que ele tera que calcular.
           MPI_Send(&divisao, 1, MPI_INT, destino, 1, MPI_COMM_WORLD);
         // Envio da tabela de custos.
           MPI_Send(&custos[0], n*n, MPI_INT, destino, 1, MPI_COMM_WORLD);
          // Envio do Vertice a ser calculado.
           MPI_Send(&vert, 1, MPI_INT, destino, 1, MPI_COMM_WORLD);

           if (vert < n)
             vert+=divisao;
          // Se tem mais processos do que vertices,envia vertice repetido.

         }
      maior = 2147483646;
      int max2;
       for (i=1; i<noProcesses; i++){
          // O vertice calculado nao é importante na resposta, por tanto não o recebemos.
          // MPI_Recv(&vert, 1, MPI_INT, i, 2, MPI_COMM_WORLD, &status);

          // Recebe a maior distancia entre o vertice e o resto do grafo.
          MPI_Recv(&max2, 1, MPI_INT, i, 2, MPI_COMM_WORLD, &status);
          // Já verifica aqui mesmo se é a menor distancia maxima, senão descarta.
          if (max2 < maior){
              maior = max2;
           }
    }
    //Imprime o resultado
    printf("Maior distancia: %d \n", maior);
   }
   else if (processId > 0)
   {
     // Os outros processos realizam o codigo abaixo.

     // Recebimento das variaveis

    MPI_Recv(&n, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
    MPI_Recv(&div, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
    MPI_Recv(&custos[0], n*n, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
    MPI_Recv(&vert, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);

     // printf("Process (%i) N (%d) Vert (%d) \n",processId,n,vert);

    // Monta um vetor dos custos dos melhores caminhos do vertice para os outros;
    int caminhosAux[MAXJUNCOES];

    int max = 0;
    maior = 2147483646;
        for(j=vert; j<vert+div; j++){
          if (j>= n) continue;
          Dijkstra(j, j, n,caminhosAux);

        // Encontra o distancia maxima dessa linha.
            for(i=0; i<n; i++){
                     // printf("%d ",caminhosAux[i]);
                if (max < caminhosAux[i])
                    max = caminhosAux[i];
            }
                     // printf(".%d.\n ",max);


         // JA verifica aqui mesmo se é a menor distancia maxima.
          if (max < maior){
              maior = max;
          }
          max = 0;
        }

      // Envio da resposta parcial ja calculada por esse vertice.
      MPI_Send(&maior, 1, MPI_INT, 0, 2, MPI_COMM_WORLD);
    }

    MPI_Finalize();

    return 0;

}
